Библиотека собеса по Java | вопросы с собеседований

❓ Как устроен HashMap под капотом?

HashMap основан на массиве бакетов (Node<K, V>[] table), где каждый бакет содержит связанный список или дерево.

🔹 Ключевые моменты

— Для хеширование ключа вызывается hashCode(), после чего вычисляется индекс массива через (n - 1) & hash, где n – размер массива.
— Если несколько ключей попадают в один бакет, создаётся связанный список. Если число элементов в бакете превысит 8, список заменяется на красно-чёрное дерево для ускорения поиска.
— Если загрузка (size / capacity) превышает 0.75, размер массива увеличивается в 2 раза, а элементы перераспределяются.
— Поиск идёт по бакету: если элементов несколько, перебирается список (или дерево), сравниваются hashCode() и equals().
— HashMap обеспечивает O(1) для операций get() / put(), но при частых коллизиях или неправильных hashCode() может деградировать до O(log n).

Please open Telegram to view this post

VIEW IN TELEGRAM

www.tg-me.com/id/Библиотека собеса по Java | вопросы с собеседований/com.java_interview_lib/779

1.9K viewsFeb 12 at 15:43

❓ Как устроен HashMap под капотом?

HashMap основан на массиве бакетов (Node<K, V>[] table), где каждый бакет содержит связанный список или дерево.

🔹 Ключевые моменты

— Для хеширование ключа вызывается hashCode(), после чего вычисляется индекс массива через (n - 1) & hash, где n – размер массива.
— Если несколько ключей попадают в один бакет, создаётся связанный список. Если число элементов в бакете превысит 8, список заменяется на красно-чёрное дерево для ускорения поиска.
— Если загрузка (size / capacity) превышает 0.75, размер массива увеличивается в 2 раза, а элементы перераспределяются.
— Поиск идёт по бакету: если элементов несколько, перебирается список (или дерево), сравниваются hashCode() и equals().
— HashMap обеспечивает O(1) для операций get() / put(), но при частых коллизиях или неправильных hashCode() может деградировать до O(log n).